Статья

Название статьи

МЕТОДИКА ВЫПОЛНЕНИЯ БАЗОВЫХ НЕМОДУЛЬНЫХ ОПЕРАЦИЙ В МОДУЛЯРНОЙ
АРИФМЕТИКЕ С ПРИМЕНЕНИЕМ ИНТЕРВАЛЬНЫХ ПОЗИЦИОННЫХ ХАРАКТЕРИСТИК

Авторы

Исупов Константин Сергеевич, аспирант, Вятский государственный университет
(Россия, г. Киров, ул. Московская, 36), isupov.k@gmail.com

Индекс УДК

004.052

Аннотация

Актуальность и цель. Системы остаточных классов (СОК) и модулярная арифметика обеспечивают возможность независимой обработки отдельных разрядов чисел и находят свое применение во многих стратегически важных областях науки, таких как криптография, цифровая обработка сигналов, высокоточные вычисления и пр. Известно, что основной проблемой эффективного использования СОК является сложность выполнения немодульных операций, требующих оценки позиционной величины модулярных чисел. Целью данной работы является теоретическое обоснование новой методики выполнения базовых немодульных операций в модулярной арифметике (сравнение, определение знака и контроль переполнения), основанной на вычислении и анализе интервальных позиционных характеристик модулярных чисел. Предлагаемая методика отличается своей простотой и позволяет асимптотически быстро получить достоверную оценку относительной позиционной величины модулярного числа.
Материалы и методы. Для решения задачи эффективного определения относительной позиционной величины числа, представленного в системе остаточных классов, использовались следствия Китайской теоремы об остатках. Для обеспечения достоверности результатов выполняемых немодульных операций использованы основные положения интервального анализа.
Результаты. Предложена новая методика выполнения немодульных операций сравнения, определения знака и контроля переполнения допустимого диапазона чисел в системах остаточных классов, основанная на вычислении и анализе интервальных позиционных характеристик модулярных чисел. Определены формальные условия корректного выполнения немодульных операций с использованием предложенного метода. Выполнен анализ трудоемкости вычисления интервальных характеристик. Получена вероятностная оценка пересечения интервальных характеристик двух модулярных чисел, приводящего к нарушению достаточных условий корректности немодульных операций.
Выводы. Операции сравнения, определения знака и контроля переполнения чисел в СОК могут быть достоверно выполнены с использованием методики оценки интервальных позиционных характеристик модулярных чисел за линейное время при последовательной реализации вычислений и логарифмическое – при параллельной. При этом не требуется больших аппаратных затрат. В отдельных случаях интервальные характеристики не позволяют однозначно определить результат немодульной операции. Вероятность возникновения таких случаев составляет(n⋅21−k ) (1− n⋅21−k ), где k – количество разрядов, отведенных для представления дробной части границ интервальных характеристик, а n – количество модулей СОК.

Ключевые слова

система остаточных классов, немодульная операция, сравнение, определение знака, контроль переполнения, интервальная позиционная характеристика, интервальный анализ.

 

 Скачать статью в формате PDF

Список литературы

1. Акушский, И. Я. Машинная арифметика в остаточных классах / И. Я. Акушский, Д. И. Юдицкий. – М. : Сов. Радио, 1968. – 440 с.
2. Omondi, A. Residue Number Systems: Theory and Implementation (Advances in Computer Science and Engineering Texts) / А. Оmondi, B. Premkumar. – London : Imperial College Press, 2007. – 312 p.
3. Червяков, Н. И. Приближенный метод выполнения немодульных операций в системе остаточных классов / Н. И. Червяков, В. М. Авербух, М. Г. Бабенко, П. А. Ляхов, А. В. Гладков, А. В. Гапочкин // Фундаментальные исследования. – 2012. – № 6 (1). – С. 189–193.
4. Koç, Ç. K. A Fast Algorithm for Mixed-Radix Conversion in Residue Arithmetic / Ç. K. Koç // Processors of the IEEE International Conference Computer Design (ICCD' 89): VLSI in Computers and Processors, October, 1989. – P. 18–21.
5. Dimauro, G. A New Technique for Fast Number Comparison in the Residue Number System / G. Dimauro, S. Impedovo, G. Pirlo // IEEE transactions on computers. – 1993. – Vol. 42, № 5. – P. 608–612.
6. Полисский, Ю. Д. Сравнение чисел в системе остаточных классов / Ю. Д. Полисский // 50 лет модулярной арифметике : юбилейная Междунар. науч.- техн. конф. – М. : МИЭТ, 2006. – С. 274–290.
7. Исупов, К. С. Способ уточненного вычисления приближенной позиционной характеристики для выполнения немодульных операций в системе остаточных классов / К. С. Исупов // Фундаментальные исследования. – 2013. – № 4 (5). – С. 796–800.
8. Кулиш, У. Достоверные вычисления. Базовые численные методы / У. Кулиш, Д. Рац, Р. Хаммер, М. Хокс ; пер. с англ. – Москва ; Ижевск : НИЦ «Регулярная и хаотическая динамика», 2005. – 496 с.
9. Шарый, С. П. Конечномерный интервальный анализ / С. П. Шарый ; ИВТ СО РАН, 2012. – 605 с. – URL: //http: www.nsc.ru/interva/
10. Kaucher, E. Interval analysis in the extended interval space IR / E. Kaucher // Computing Supplement. – 1989 – Vol. 2. – P. 33–49.

 

Дата создания: 26.02.2014 17:36
Дата обновления: 03.03.2014 16:05